package leetcode_200;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 *@author 周杨
 *WordLadder_127 广度遍历
 *describe:用队列 AC 77%
 *2018年5月26日 上午11:06:07
 */
public class WordLadder_127 {

	public static void main(String[] args) {
		WordLadder_127 test=new WordLadder_127();
		List<String> wordList=new ArrayList<String>();
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");
		System.out.println(test.ladderLength("hit", "cog", wordList));

	}
	
	/**
	 * describe:用层次遍历的思想  不知为何超时
	 * 2018年5月26日 上午9:57:31
	 */
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if(wordList==null)
			return 0;
		int len=beginWord.length();
		Set<String> set=new HashSet<String>(wordList);
		set.remove(beginWord);
		Queue<String> queue=new LinkedList<String>();
		queue.add(beginWord);
		int res=0;
		while(!queue.isEmpty()) {
			int count=queue.size();
			++res;
			while(count>0) {
				String now=queue.poll();
				//System.out.println("out  "+now);
				for(int i=0;i<len;++i) {
					char [] chars=now.toCharArray();
					for(char j='a';j<='z';++j) {
						chars[i]= j; 
						String temp=new String(chars);
						if(set.contains(temp)) {
							if(temp.equals(endWord))
								return res+1;
							queue.add(temp);
							set.remove(temp);
							//System.out.println("In  "+temp );
						}
					}
				}
				
				--count;
			}
		}
		
		return 0;
	}
	
	/**
	 * describe:层次遍历
	 * 2018年5月26日 上午10:08:25
	 */
	public int ladderLength1(String beginWord, String endWord, List<String> wordList) {  
        if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0  
                || beginWord.length() != endWord.length())  
            return 0;  
        // 此题关键是去重，还有去除和beginWord，相同的单词  
        Set<String> set = new HashSet<String>(wordList);  
        if (set.contains(beginWord))  
            set.remove(beginWord);  
        Queue<String> wordQueue = new LinkedList<String>();  
        int level = 1; // the start string already count for 1  
        int curnum = 1;// the candidate num on current level  
        int nextnum = 0;// counter for next level  
        // 或者使用map记录层数  
        // Map<String, Integer> map = new HashMap<String, Integer>();  
        // map.put(beginWord, 1);  
        wordQueue.add(beginWord);  
  
        while (!wordQueue.isEmpty()) {  
            String word = wordQueue.poll();  
            curnum--;  
            // int curLevel = map.get(word);  
            for (int i = 0; i < word.length(); i++) {  
                char[] wordunit = word.toCharArray();  
                for (char j = 'a'; j <= 'z'; j++) {  
                    wordunit[i] = j;  
                    String temp = new String(wordunit);  
  
                    if (set.contains(temp)) {  
                        if (temp.equals(endWord))  
                            // return curLevel + 1;  
                            return level + 1;  
                        // map.put(temp, curLevel + 1);  
                        nextnum++;  
                        wordQueue.add(temp);  
                        set.remove(temp);  
                    }  
                }  
            }  
            if (curnum == 0) {  
                curnum = nextnum;  
                nextnum = 0;  
                level++;  
            }  
        }  
        return 0;  
    }  

}
